home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / 2DLab / edgelist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-01-14  |  3.5 KB  |  150 lines
  1. #include "voronoi.h"
  2.  
  3. int ntry, totalsearch;
  4.  
  5. void ELinitialize()
  6. {
  7.     int i;
  8.  
  9.     freeinit(&hfl, sizeof **ELhash);
  10.     ELhashsize = 2 * sqrt_nsites;
  11.     ELhash = (struct Halfedge **) myalloc ( sizeof (*ELhash) * ELhashsize);
  12.     for(i=0; i<ELhashsize; i +=1) 
  13.     ELhash[i] = (struct Halfedge *)NULL;
  14.     ELleftend = HEcreate( (struct Edge *)NULL, 0);
  15.     ELrightend = HEcreate( (struct Edge *)NULL, 0);
  16.     ELleftend->ELleft = (struct Halfedge *)NULL;
  17.     ELleftend->ELright = ELrightend;
  18.     ELrightend->ELleft = ELleftend;
  19.     ELrightend->ELright = (struct Halfedge *)NULL;
  20.     ELhash[0] = ELleftend;
  21.     ELhash[ELhashsize-1] = ELrightend;
  22. }
  23.  
  24. struct Halfedge *HEcreate(e, pm)
  25. struct Edge *e;
  26. int pm;
  27. {
  28.     struct Halfedge *answer;
  29.  
  30.     answer = (struct Halfedge *) getfree(&hfl);
  31.     answer->ELedge = e;
  32.     answer->ELpm = pm;
  33.     answer->PQnext = (struct Halfedge *) NULL;
  34.     answer->vertex = (struct Site *) NULL;
  35.     answer->ELrefcnt = 0;
  36.     return(answer);
  37. }
  38.  
  39. ELinsert(lb, new)
  40. struct    Halfedge *lb, *new;
  41. {
  42.     new->ELleft = lb;
  43.     new->ELright = lb->ELright;
  44.     (lb->ELright)->ELleft = new;
  45.     lb->ELright = new;
  46. }
  47.  
  48. /* Get entry from hash table, pruning any deleted nodes */
  49. struct Halfedge *ELgethash(b)
  50. int b;
  51. {
  52.     struct Halfedge *he;
  53.  
  54.     if(b<0 || b>=ELhashsize) 
  55.     return((struct Halfedge *) NULL);
  56.     he = ELhash[b]; 
  57.     if (he == (struct Halfedge *)NULL || he->ELedge!=(struct Edge *)DELETED) 
  58.     return (he);
  59.  
  60. /* Hash table points to deleted half edge.  Patch as necessary. */
  61.     ELhash[b] = (struct Halfedge *) NULL;
  62.     if ((he->ELrefcnt -= 1) == 0) makefree(he, &hfl);
  63.     return ((struct Halfedge *) NULL);
  64. }    
  65.  
  66. struct Halfedge *ELleftbnd(p)
  67. struct Point *p;
  68. {
  69.     int i, bucket;
  70.     struct Halfedge *he;
  71.  
  72. /* Use hash table to get close to desired halfedge */
  73.     bucket = (p->x - xmin)/deltax * ELhashsize;
  74.     if(bucket<0) 
  75.     bucket =0;
  76.     if(bucket>=ELhashsize) 
  77.     bucket = ELhashsize - 1;
  78.     he = ELgethash(bucket);
  79.     if(he == (struct Halfedge *) NULL) {   
  80.     for(i=1; 1 ; i += 1) {    
  81.         if ((he=ELgethash(bucket-i)) != (struct Halfedge *) NULL) 
  82.         break;
  83.         if ((he=ELgethash(bucket+i)) != (struct Halfedge *) NULL) 
  84.         break;
  85.     }
  86.     totalsearch += i;
  87.     }
  88.     ntry += 1;
  89.  
  90. /* Now search linear list of halfedges for the corect one */
  91.     if (he==ELleftend  || (he != ELrightend && right_of(he,p))) {
  92.     do {
  93.         he = he->ELright;
  94.     } while (he!=ELrightend && right_of(he,p));
  95.          he = he->ELleft;
  96.     } else 
  97.     do {
  98.         he = he->ELleft;
  99.     } while (he!=ELleftend && !right_of(he,p));
  100.  
  101. /* Update hash table and reference counts */
  102.     if(bucket > 0 && bucket <ELhashsize-1) {    
  103.     if(ELhash[bucket] != (struct Halfedge *) NULL) 
  104.         ELhash[bucket]->ELrefcnt -= 1;
  105.     ELhash[bucket] = he;
  106.     ELhash[bucket]->ELrefcnt += 1;
  107.     }
  108.     return (he);
  109. }
  110.  
  111. /*
  112.  *  This delete routine can't reclaim node, since pointers from hash
  113.  *  table may be present.   
  114.  */
  115. ELdelete(he)
  116. struct Halfedge *he;
  117. {
  118.     (he->ELleft)->ELright = he->ELright;
  119.     (he->ELright)->ELleft = he->ELleft;
  120.     he->ELedge = (struct Edge *)DELETED;
  121. }
  122.  
  123. struct Halfedge *ELright(he)
  124. struct Halfedge *he;
  125. {
  126.     return (he->ELright);
  127. }
  128.  
  129. struct Halfedge *ELleft(he)
  130. struct Halfedge *he;
  131. {
  132.     return (he->ELleft);
  133. }
  134.  
  135. struct Site *leftreg(he)
  136. struct Halfedge *he;
  137. {
  138.     if(he->ELedge == (struct Edge *)NULL) 
  139.     return(bottomsite);
  140.     return( he->ELpm == le ? he->ELedge->reg[le] : he->ELedge->reg[re]);
  141. }
  142.  
  143. struct Site *rightreg(he)
  144. struct Halfedge *he;
  145. {
  146.     if(he->ELedge == (struct Edge *)NULL) 
  147.     return(bottomsite);
  148.     return( he->ELpm == le ? he->ELedge->reg[re] : he->ELedge->reg[le]);
  149. }
  150.